package _binary_search;

/**
 * 1533. 找到最大整数的索引
 */
public class No1533 {
    public int getIndex(ArrayReader reader) {
        int left = 0, right = reader.length() - 1;
        while (true) {
            int mid = left + (right - left) / 2;
            // 比较左右两端值大小。偶数情况右值去掉中间值，保持两边值数量一致
            int compared = reader.compareSub(left, mid, mid + ((right - left) & 1), right);
            if (compared == -1) left = mid + 1;
            else if (compared == 1) right = mid;
            else return mid;
        }
    }

    interface ArrayReader {
        /**
         * Compares the sum of arr[l..r] with the sum of arr[x..y]
         * return 1 if sum(arr[l..r]) > sum(arr[x..y])
         * return 0 if sum(arr[l..r]) == sum(arr[x..y])
         * return -1 if sum(arr[l..r]) < sum(arr[x..y])
         */
        default int compareSub(int l, int r, int x, int y) {
            return 0;
        }

        /**
         * Returns the length of the array
         */
        default int length() {
            return 0;
        }
    }
}
